\documentclass[letterpaper, 12pt, oneside]{tesis}
\graphicspath{{figuras/}}

\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[fixlanguage]{babelbib}
\usepackage{paquetes/hyphenat}

\usepackage{natbib}
\usepackage{verbatim}
\usepackage{tikz}
\usepackage{fancyvrb}
\usepackage{enumerate}
\usepackage{paquetes/vector}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{paquetes/algorithmic}
\usepackage{paquetes/algorithm}
\usepackage{float}
\usepackage{paquetes/epigraph}
\usepackage{array}
\usepackage{tabularx}
\usepackage{caption}
\usepackage{paquetes/multirow}
\usepackage{lscape}
\usepackage{mdframed}

%:%s/\(bibitem.\+\)and/\1y/g
%\usepackage[letterpaper, inner=3cm, outer=2cm]{geometry}
%\addtolength[\topmargin]{-1.5cm}
%\addtolength[\textheight]{4cm}

%\usepackage{setspace,cite} % Doble espacio para texto, espacio singular para
                           % los caption y pie de pagina

\hypersetup{urlcolor=blue, colorlinks=false}
\numberwithin{algorithm}{chapter}

\newcommand{\ALG}{Lista de Algoritmos}
\renewcommand*\listalgorithmname{\ALG}
\renewcommand{\tablename}{Tabla}
\renewcommand{\spanishtablename}{Tabla}
\renewcommand*\listtablename{Lista de Tablas}
\newcommand\listsymbolname{Acrónimos}
\newcommand{\tup}[1]{\langle #1 \rangle}
\floatname{algorithm}{Algoritmo}
\newcommand{\A}{\ensuremath{\mathcal{A}}}
\newcommand{\LPO}{\text{LPO}}
\newcommand{\LSO}{\text{LSO}}
\newcommand{\SO}{\ensuremath{\text{SO}}}
\newcommand{\SOE}{\ensuremath{\text{SO}\exists}}
\newcommand{\SOA}{\ensuremath{\text{SO}\forall}}
\newcommand{\SOEA}{\ensuremath{\text{SO}\exists\forall}}
\newcommand{\SOAEA}{\ensuremath{\text{SO}\forall\exists\forall}}
\newcommand{\Q}{\ensuremath{\mathcal{Q}}}
\newcommand{\struc}{\text{STRUC}}
\newcommand{\FT}{\ensuremath{\mathfrak{F}}}
\newcommand{\eq}{\equiv}
\renewcommand{\models}{\vDash}
\newcommand{\domred}{\mathfrak{D}}
\newcommand{\insred}{\mathfrak{I}}
\newcommand{\domain}{\mathsf{dom}}
\newcommand{\instance}{\mathsf{ins}}
\newcommand{\ground}{\mathfrak{G}}
\newcommand{\fttt}[1]{{\texttt{\footnotesize #1}}}
\newcommand{\prove}{{\texttt{\footnotesize prove}}}
\renewcommand{\t}{\ensuremath{\tau}}

\parindent 3ex % Agrega sangrías de 3 espacios (3 veces el espacio de la x)
\setlength{\baselineskip}{1.5pt} % Interlineado 1.5
\setlength{\parskip}{16.5pt} % Interparrafo 16.5pt
%\oddsidemargin 3cm
\topmargin 2cm

% Grammar
\newcommand{\deriv}{\longrightarrow}
% non-terminals
\newcommand{\sofbf}{\ensuremath{\langle\textsf{fbf-so}\rangle}}
\newcommand{\listrel}{\ensuremath{\langle\textsf{lista-rel}\rangle}}
\newcommand{\pofbf}{\ensuremath{\langle\textsf{fbf-po}\rangle}}
\newcommand{\listvar}{\ensuremath{\langle\textsf{lista-var}\rangle}}
\newcommand{\qffbf}{\ensuremath{\langle\textsf{qf-fbf}\rangle}}
\newcommand{\listpofbf}{\ensuremath{\langle\textsf{lista-fbf-po}\rangle}}
\newcommand{\atom}{\ensuremath{\langle\textsf{atom}\rangle}}
\newcommand{\tipof}{\ensuremath{\langle\textsf{tipo-fun}\rangle}}

% terminals
\newcommand{\lpar}{\texttt{(}}
\newcommand{\rpar}{\texttt{)}}
\newcommand{\AND}{\texttt{and}}
\newcommand{\OR}{\texttt{or}}
\newcommand{\NOT}{\texttt{not}}
\newcommand{\IMPLIES}{\texttt{implies}}
\newcommand{\SOExists}{\texttt{so-exists}}
\newcommand{\SOForall}{\texttt{so-forall}}
\newcommand{\Exists}{\texttt{exists}}
\newcommand{\Forall}{\texttt{forall}}
\newcommand{\Inj}{\text{Inj}}
\newcommand{\Fun}{\text{Fun}}
\newcommand{\PFun}{\text{PFun}}
\newcommand{\PInj}{\text{PFun}}

% tokens
\newcommand{\var}{\texttt{<VAR>}}
\newcommand{\const}{\texttt{<CONST>}}
\newcommand{\rel}{\texttt{<REL>}}
\newcommand{\integer}{\texttt{<int>}}
\newcommand{\fsymbol}{\texttt{<FUNC>}}

% holds
\newcommand{\holds}[2]{\ensuremath{\textbf{holds}[#1](#2)}}
\newcommand{\action}[4]{\ensuremath{\textbf{set}[#1](#2): \textbf{pre}=\{#3\},\ \textbf{add}=\{#4\}}}

% translation
\newcommand{\F}{\mathbb{F}}
\newcommand{\Not}{\text{not-}}
%\newcommand{\est}[4]{\textbf{est}[#1](#2): \textbf{pre}=\{#3\},\ \textbf{add}=\{#4\}}
\newcommand{\est}[4]{\textbf{establish}[#1](#2)=(\{#3\},\{#4\})}
\newcommand{\settrue}[3]{\textbf{set-true}[#1](#2)=(\emptyset,\{#3\})}
\newcommand{\setfalse}[3]{\textbf{set-false}[#1](#2)=(\emptyset,\{#3\})}
\newcommand{\SUC}{\text{SUC}}
\newcommand{\len}{\ell}

%\newcommand{\action}[1]{action[#1]}
\newcommand{\pre}{\text{pre}}
\newcommand{\eff}{\text{eff}}
\newcommand{\true}{\textbf{true}}
\newcommand{\false}{\textbf{false}}
\newcommand{\SAT}{\textsc{Sat}}
\newcommand{\CLIQUE}{\textsc{Clique}}
\newcommand{\CHD}{\textsc{CHD}}
\newcommand{\TDM}{\textsc{3DM}}
\newcommand{\TCOL}{\textsc{3Col}}
\newcommand{\KCOL}{\ensuremath{k\textsc{Col}}}
\newcommand{\qAE}{\ensuremath{\forall\exists}\xspace}
\newcommand{\qEA}{\ensuremath{\exists\forall}\xspace}
\newcommand{\qEAE}{\ensuremath{\exists\forall\exists}\xspace}
\newcommand{\qAEA}{\ensuremath{\forall\exists\forall}\xspace}
\newcommand{\coCOL}{\ensuremath{\overline{\text{3Col}}}\xspace}
\newcommand{\STRIPS}{\text{STRIPS}\xspace}
\newcommand{\TC}{\text{TC}}
\newcommand{\PH}{\ensuremath{\text{PH}}\xspace}
\newcommand{\PSPACE}{\text{PSPACE}\xspace}
\newcommand{\UNSAT}{\textsc{Unsat}}

\renewcommand{\O}{\ensuremath{\mathcal{O}}}
\newcommand{\pwin}{long}


%! referencias manera estandar

%%%% Título
\begin{titlepage}
	\title{\vspace{-2cm} \includegraphics[width=1.2in]{./usb.png} \\[.2cm]
		\large Universidad Simón Bolívar \\
		Decanato de Estudios Profesionales \\
		Coordinación de Ingeniería de la Computación
		\vfill
		\LARGE Reducciones automáticas de problemas de decisión a problemas de
        planificación \vfill}
	\author{Por: \\
		Aldo Fabrizio Porco Rametta \\
		Alejandro Machado González \\[1.2cm]
		Realizado con la asesoría de: \\
		Prof. Blai Bonet\\[1.2cm]
		PROYECTO DE GRADO \\
Presentado ante la Ilustre Universidad Simón Bolívar \\
como requisito parcial para optar al título de \\
Ingeniero de Computación}
    \date{Sartenejas, febrero de 2013}
\end{titlepage}
%%%% Título

\begin{document}

\frontmatter

\maketitle
\setstretch{1.3}

%% Define the page headers using the FancyHdr package and set up for one-sided printing
%\fancyhead{}  % Clears all page headers and footers
%\rhead{\thepage}  % Sets the right side header to show the page number
%\lhead{}  % Clears the left side page header
%
%\pagestyle{fancy}  % Finally, use the "fancy" page style to implement the FancyHdr headers
%
%%% ----------------------------------------------------------------
%% The "Funny Quote Page"
%\setcounter{page}{2}
%\pagestyle{empty}  % No headers or footers for the following pages
%
%\null\vfill
%% Now comes the "Funny Quote", written in italics
%\textit{``El hombre razonable se adapta al mundo; el irrazonable intenta adaptar
%el mundo a si mismo. Así pues, el progreso depende del hombre irrazonable.''}
%
%\begin{flushright}
%George Bernard Shaw
%\end{flushright}
%
%\vfill\vfill\vfill\vfill\vfill\vfill\null
%\clearpage  % Funny Quote page ended, start a new page
%%% ----------------------------------------------------------------
%
%%% ----------------------------------------------------------------

%The Abstract Page

\addtotoc{Resumen}  % Add the "Abstract" page entry to the Contents
\abstract{
\addtocontents{toc}{\vspace{1em}}  % Add a gap in the Contents, for aesthetics
Este trabajo tiene como objetivo el desarrollo de una herramienta que permita
establecer una correspondencia entre problemas de decisión expresados en un 
lenguaje descriptivo y problemas de planificación automática.
Notando que existen problemas que son modelables más naturalmente utilizando la
lógica, la motivación del trabajo es proporcionar una forma de
solucionar estos problemas especificados de una manera declarativa.

Para lograr esta meta se diseñaron dos reducciones orientadas específicamente a
las clases de complejidad NP y PH, utilizando los formalismos de la Teoría de
Complejidad Descriptiva que establece equivalencias entre lógicas de distintos
poderes expresivos con clases de complejidad computacionales. Como los
problemas de planificación automática son en general PSPACE-completos, es
de interés observar que la primera traducción produce problemas de
planificación restringidos que pertenezcan también a la clase NP, de modo que
la resolución de problemas no sea más compleja de lo necesaria a causa de la reducción.

La herramienta desarrollada consta de un analizador sintáctico de un lenguaje
basado en la lógica de segundo orden y de una serie de recorridos del
árbol sintáctico para generar un problema de planificación STRIPS, expresado en lenguaje PDDL. Un aspecto
importante de la herramienta es que cumple con las propiedades formales
postuladas en el Teorema \ref{principal}, que acotan su complejidad.

Se modelaron y solucionaron problemas de varios dominios y tamaños a modo de
probar la efectividad de un planificador basado en SAT para resolver los
problemas traducidos. Los resultados fueron satisfactorios para problemas
pequeños: el planificador logró resolver la mayoría de ellos en menos de
cinco minutos.

Parte de este trabajo fue presentado en la \textit{21st International
Conference on Automated Planning and Scheduling} (ICAPS 2011), y
los investigadores del área han reconocido que los dominios generados por la 
herramienta son de interés práctico, pues se conocen sus propiedades formales y 
es posible estudiarlos a fondo para descubrir mejores heurísticas y optimizaciones para los
planificadores.

\noindent \begin{small} \textbf{Palabras clave}: Planificación Automática, Teoría de
Complejidad, Lógica, Ingeniería del Conocimiento, Inteligencia Artificial.
\end{small}

\clearpage % Abstract ended, start a new page
%% ----------------------------------------------------------------

\setstretch{1.3}  % Reset the line-spacing to 1.3 for body text (if it has changed)

% The Acknowledgements page, for thanking everyone
%\acknowledgements{
%\addtocontents{toc}{\vspace{1em}}  % Add a gap in the Contents, for aesthetics
%Agradecimientos aquí.
%}

%\clearpage  % End of the Acknowledgements

\pagestyle{fancy}  %The page style headers have been "empty" all this time, now use the "fancy" headers as defined before to bring them back

%% ----------------------------------------------------------------
\lhead{\emph{Índice General}}  % Set the left side page header to "Contents"
\tableofcontents  % Write out the Table of Contents

%% ----------------------------------------------------------------
\lhead{\emph{Índice de Figuras}}  % Set the left side page header to "List if figuras" 
\listoffigures  % Write out the List of figuras

%% ----------------------------------------------------------------
\lhead{\emph{Índice de Tablas}}  % Set the left side page header to "List of Tables"
\renewcommand*\listtablename{Lista de Tablas}
\listoftables  % Write out the List of Tables

%% ----------------------------------------------------------------
%\lhead{\emph{Lista de Algoritmos}} % Set the left side page header to "List of Algorithms"
%\addtotoc{Lista de Algoritmos}
%\listofalgorithms % Write out the List of Algorithms

%% ----------------------------------------------------------------
\setstretch{1.5}  % Set the line spacing to 1.5, this makes the following tables easier to read
\clearpage  % Start a new page
\lhead{\emph{Acrónimos y símbolos}}  % Set the left side page header to "Abbreviations"
\listofsymbols{ll}  % Include a list of Abbreviations (a table of two columns)
{
% \textbf{Acronym} & \textbf{W}hat (it) \textbf{S}tands \textbf{F}or \\
\textbf{3Col} & \textbf{3}-\textbf{Col}orabilidad\\
\textbf{3DM} & \textbf{3}-\textbf{D}imensional \textbf{M}atching\\
\textbf{CHD} & \textbf{C}amino \textbf{H}amiltoniano \textbf{D}irigido\\
\textbf{BNF} & \textbf{B}ackus-\textbf{N}aur \textbf{F}orm\\
\textbf{CNF} & \textbf{C}onjunctive \textbf{N}ormal \textbf{F}orm\\
\textbf{kCol} & $k$-\textbf{Col}orabilidad\\
\textbf{LPO} & \textbf{L}ógica de \textbf{P}rimer \textbf{O}rden\\
\textbf{LSO} & \textbf{L}ógica de \textbf{S}egundo \textbf{O}rden\\
\textbf{NP} & \textbf{N}ondeterministic \textbf{P}olynomial time (clase de complejidad)\\
\textbf{PDDL} & \textbf{P}lanning \textbf{D}omain \textbf{D}efinition \textbf{L}anguage \\
\textbf{PH} & \textbf{P}olynomial \textbf{H}ierarchy (clase de complejidad)\\
\textbf{QBF} & \textbf{Q}uantified \textbf{B}oolean \textbf{F}ormula\\
\textbf{SAT} & boolean \textbf{SAT}isfiability\\
\textbf{STRIPS} & \textbf{S}tanford \textbf{R}esearch \textbf{I}nstitute \textbf{P}roblem \textbf{S}olver\\
\textbf{TCD} & \textbf{T}eoría de \textbf{C}omplejidad \textbf{D}escriptiva\\
%&\\
%\hline
%&\\
%\textbf{Fun} & abreviación de función total\\
%\textbf{Inj} & abreviación de función total inyectiva\\
%\textbf{PFun} & abreviación de función parcial\\
%\textbf{PInj} & abreviación de función parcial inyectiva\\
&\\
\hline
&\\
$\iff$ & doble implicación, si y sólo si\\
$\Rightarrow$ & implicación lógica\\
$[u:=v]$ & sustitución textual de $u$ por $v$
}

%% ----------------------------------------------------------------
% End of the pre-able, contents and lists of things
% Begin the Dedication page

\setstretch{1.3}  % Return the line spacing back to 1.3

\pagestyle{empty}  % Page style needs to be empty for this page
%\dedicatory{Dedicated to adventures...\ldots}

\addtocontents{toc}{\vspace{2em}}  % Add a gap in the Contents, for aesthetics

%% ----------------------------------------------------------------
\mainmatter	  % Begin normal, numeric (1,2,3...) page numbering
\pagestyle{fancy}  % Return the page headers back to the "fancy" style

% Include the chapters of the thesis, as separate files
% Just uncomment the lines as you write the chapters

\input{./capitulos/introduccion}
\input{./capitulos/capitulo1}
\input{./capitulos/capitulo2}
\input{./capitulos/capitulo3}
\input{./capitulos/capitulo4}
\input{./capitulos/conclusiones}

%% ----------------------------------------------------------------
%the Bibliography 
\label{Bibliography}
\bibliography{bibliografia}  % The references (bibliography) information are stored in the file named "Bibliography.bib"
\lhead{\emph{Bibliografía}}  % Change the left side page header to "Bibliography"
\bibliographystyle{aaai}  % Use the "unsrtnat" BibTeX style


%% ----------------------------------------------------------------
% Now begin the Appendices, including them as separate files

\addtocontents{toc}{\vspace{2em}} % Add a gap in the Contents, for aesthetics

\appendix % Cue to tell LaTeX that the following 'chapters' are Appendices

\input{./apendices/apendiceA}
\input{./apendices/apendiceB}

\addtocontents{toc}{\vspace{2em}}  % Add a gap in the Contents, for aesthetics
\backmatter

\end{document}
